package graph;

import java.util.*;

/**
 * @author Autumn Whispser
 * @param <V>
 */
public class Graph<V> {
    /*将顶点按顺序编号 */
    //构造点集--实际编号和具体的数据关联起来。
    HashMap<Integer, Node<V>> nodes;
    //存储边集
    HashSet<Edge<V>> edges;
    //构造函数
    public Graph() {
        //初始化点集和边集/
        nodes = new HashMap<Integer, Node<V>>();
        edges = new HashSet<Edge<V>>();
    }
    //获取顶点数量
    public int size() {
        return nodes.size();
    }
    //获取边的数量
    public int sizeOfEdge(){
        return edges.size();
    }
    public boolean addNode(Integer id, V value) {
        if (!nodes.containsKey(id)) {
            nodes.put(id,new Node<V>(id,value));
            return true;//删除成功
        }
        return false;//删除结点不存在
    }
    public boolean addEdge(Integer from, Integer to, int weight) {
        Node<V> fromNode = nodes.get(from);
        Node<V> toNode = nodes.get(to);
        if(fromNode != null && toNode != null){
            Edge<V> edge = new Edge<>(fromNode, toNode, weight);
            edges.add(edge);//边集新添一条边
            fromNode.addNeighbor(toNode);
            fromNode.addEdge(edge);
            return true;//删除成功
        }
        return false;//删除结点不存在
    }
    // 删除节点
    public void removeNode(Integer id) {
        //移除点集的结点， 并且获取该值以待后续处理。
        Node<V> nodeToRemove = nodes.remove(id);
        //删除结点是存在的， 则执行删除
        if (nodeToRemove != null) {
            // 边集:删除与该节点相关的所有边---for each循环实现
            for (Edge<V> edge : new HashSet<>(edges)) {
                if (edge.getFrom() == nodeToRemove || edge.getTo() == nodeToRemove) {
                    edges.remove(edge);
                }
            }
            // 更新移除结点所有邻居的入度。 移除的nodeToRemove不需要处理。
            for (Node<V> neighbor : nodeToRemove.getNexts()) {
                neighbor.in--;
            }
        }
    }
    /*给定两个结点的编号， 删除它们之间关联的边 */
    public void removeEdge(Integer fromId, Integer toId){
        //获取编号对应的结点
        Node<V> fromNode = nodes.get(fromId);
        Node<V> toNode = nodes.get(toId);
        //结点均不为空
        if(fromNode != null && toNode != null){
            Edge<V> edgeToRemove = null;//遍历边集获取这条边。
            for (Edge<V> edge : edges) {
                if (edge.getFrom() == fromNode && edge.getTo() == toNode) {
                    edgeToRemove = edge;
                    break;
                }
            }
            //判断是否找到了， 找到了执行删除。
            if (edgeToRemove != null) {
                edges.remove(edgeToRemove);//在边集内部移除这条边。
                //更新起点fromNode的edges, 从其关联边里删除
                fromNode.edges.remove(edgeToRemove);
                toNode.in--; // 更新入度
                fromNode.out--; // 更新出度
            }
        }
    }

//    @Override
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//        Graph<?> graph = (Graph<?>) o;
//
//    }
    public boolean isSameGraph(Graph<V> other) {
        if (nodes.size() != other.nodes.size() || edges.size() != other.edges.size()) {
            return false; // 如果节点或边的数量不同，直接返回 false
        }
        //检查点集
        for (Map.Entry<Integer, Node<V>> entry : nodes.entrySet()) {
            Node<V> otherNode = other.nodes.get(entry.getKey());
            if (otherNode == null || !entry.getValue().value.equals(otherNode.value)) {
                return false; // 检查节点的值
            }
        }

        // 检查边
        for (Edge<V> edge : edges) {
            Edge<V> otherEdge = other.edges.stream()
                    .filter(e -> e.from.id == edge.from.id && e.to.id == edge.to.id)
                    .findFirst().orElse(null);
            if (otherEdge == null || edge.weight != otherEdge.weight) {
                return false; // 检查边的权重
            }
        }
        return true;
    }
    /**
     * 该方法会合并另一个图. 进行深拷贝。
     * 这里假定编码唯一。重复了的id则不添加。
     * @param other 另一个图
     */
   public void union(Graph<V> other) {
       if(!isSameGraph(other)){
           return ;//相同图不用合并。
       }
        Graph<V> newGraph = other.deepCopy();
        //合并点集
       for(Map.Entry<Integer, Node<V>> entry : newGraph.nodes.entrySet()){
           Integer id = entry.getKey();
           if(!nodes.containsKey(id)){
               Node<V> node = entry.getValue();
               nodes.put(id,node);
           }
       }
       // 合并边集，避免重复边
       for (Edge<V> edge : newGraph.edges) {
           if (!edges.contains(edge)) {
               edges.add(edge);
               edge.from.addEdge(edge); // 更新起点的边
               edge.from.addNeighbor(edge.to); // 更新邻接关系
           }
       }

   }
    public void contractNodes(Node<V> u, Node<V> v) {
        if (u == null || v == null || u == v) {
            return; // 空引用或自环的情况无法进行边收缩。
        }

        // 合并两个顶点的值
        V newValue = mergeValues(u.getValue(), v.getValue());
        // 创建新节点，使用其中一个顶点的ID
        Node<V> newNode = new Node<>(u.getId(), newValue);

        // 更新边的起点和终点
        for (Edge<V> edge : edges) {
            if (edge.from == u || edge.from == v) {
                edge.from = newNode;
            }
            if (edge.to == u || edge.to == v) {
                edge.to = newNode;
            }
        }

        // 删除原有的节点
        nodes.remove(u.id);
        nodes.remove(v.id);

        // 添加新节点到图中
        nodes.put(newNode.id, newNode);
    }

    private V mergeValues(V value1, V value2) {
        // 自定义合并逻辑
        // 例如，可以选择返回一个合并后的值，或根据特定规则进行选择
        return value1; // 示例：简单返回第一个值
    }

    public Graph<V> deepCopy() {
        Graph<V> newGraph = new Graph<>();

        // 先深拷贝点集:复制节点
        for (Map.Entry<Integer, Node<V>> entry : nodes.entrySet()) {
            Node<V> originalNode = entry.getValue();
            Node<V> newNode = new Node<>(originalNode.id, originalNode.value);
            newGraph.nodes.put(entry.getKey(), newNode);
        }

        // 然后复制边并建立关联
        //遍历原图的边， 获取权重， 根据id来建立新节点的联系。 保证新节点关联边与原图逻辑上是一致的。
        for (Edge<V> edge : edges) {
            //根据编号id操作新图

            //操作新图， 根据id获取起点终点，两个图建立联系是通过id。
            Node<V> fromNode = newGraph.nodes.get(edge.from.id);
            Node<V> toNode = newGraph.nodes.get(edge.to.id);
            Edge<V> newEdge = new Edge<>(fromNode, toNode, edge.weight);
            newGraph.edges.add(newEdge);
            fromNode.addEdge(newEdge); // 更新起点的边
            fromNode.addNeighbor(toNode); // 更新邻接关系
        }

        return newGraph;
    }
    /*查找*/
    Edge<V> searchEdge(Node<V> from, Node<V> to){
       for (Edge<V> edge : edges) {
           if (edge.getFrom() == from && edge.getTo() == to) {
               return edge;
           }
       }
       return null;
    }
    /*查找带权边 */
    Edge<V> searchEdgeWithWeight(Node<V> from, Node<V> to, int weight){
       for (Edge<V> edge : edges) {
           if (edge.getFrom() == from && edge.getTo() == to && edge.getWeight() == weight) {
               return edge;
           }
       }
       return null;
    }
}